import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;


public class Main {

	/**
	 * @param args
	 */
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int testCases = Integer.parseInt(br.readLine());
		while(testCases-- != 0) {
			String hw = br.readLine();
			StringTokenizer sToken = new StringTokenizer(hw, " ");
			int h = Integer.parseInt(sToken.nextToken());
			int w = Integer.parseInt(sToken.nextToken());
			int[][] memoMatrix = new int[h][w];
			for(int i = 0; i < h; i++) {
				String st = br.readLine();
				sToken = new StringTokenizer(st, " ");
				for(int j = 0; j < w && sToken.hasMoreTokens(); j++) {
					memoMatrix[i][j] = Integer.parseInt(sToken.nextToken());
				}
			}
			
			
			for(int i=1; i<h; i++) {
				for(int j=0; j<w; j++) {
					memoMatrix[i][j] = memoMatrix[i][j] + findMax(memoMatrix[i - 1][j], (j - 1 >= 0 ? memoMatrix[i - 1][j - 1] : Integer.MIN_VALUE) , (j + 1 < w ? memoMatrix[i - 1][j + 1] : Integer.MIN_VALUE));
				}
			}
			
			int max = Integer.MIN_VALUE;
			for(int j=0; j < w; j++) {
				max = Math.max(max, memoMatrix[h - 1][j]);
			}
			System.out.println(max);
		}
	}
	
	private static int findMax(int x, int y, int z) {
		return Math.max(Math.max(x, y), z);
	
	}

}

